import sortedcontainers


class Solution(object):
    def avoidFlood(self, rains):
        n = len(rains)
        ans = [-1] * n
        d = {}
        r = sortedcontainers.SortedList()
        for i in range(n):
            if rains[i] == 0:
                r.add(i)
            else:
                if rains[i] in d:
                    index = r.bisect_right(d[rains[i]])
                    if index < len(r):
                        node = r.pop(index)
                        ans[node] = rains[i]
                    else:
                        return []
                d[rains[i]] = i
        for node in r:
            ans[node] = 1
        return ans


data = Solution()
rains = [1, 0, 2, 0, 3, 0, 2, 0, 0, 0, 1, 2, 3]
print(data.avoidFlood(rains))
